import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author Pavel Belevich
 *         Date: Sep 19, 2012
 *         Time: 11:13:47 AM
 */
@SuppressWarnings({ "UnusedDeclaration" })
public class RandomizedQueue<Item> implements Iterable<Item> {

    private Item[] items = (Item[]) new Object[1];
    private int N;
    
    // construct an empty randomized queue
    public RandomizedQueue() {

    }

    // is the queue empty?
    public boolean isEmpty() {
        return 0 == N;
    }

    // return the number of items on the queue
    public int size() {
        return N;
    }

    // add the item
    @SuppressWarnings({ "ManualArrayCopy" })
    public void enqueue(Item item) {
        if (null == item) throw new NullPointerException();
        if (this.items.length == N) {
            Item[] newItems = (Item[]) new Object[2*N];
            for (int i = 0; i < N; i++) {
                newItems[i] = this.items[i];
            }
            this.items = newItems;
        }
        this.items[N] = item;
        int k = StdRandom.uniform(N+1);
        Item tmp = items[k];
        this.items[k] = this.items[N];
        this.items[N++] = tmp;
    }

    // delete and return a random item
    @SuppressWarnings({ "unchecked", "ManualArrayCopy" })
    public Item dequeue() {
        if (this.isEmpty()) throw new NoSuchElementException();
        if (this.items.length / 4 == N) {
            Item[] newItems = (Item[]) new Object[2*N];
            for (int i = 0; i < N; i++) {
                newItems[i] = this.items[i];
            }
            this.items = newItems;
        }
        int last = --N;
        Item result = this.items[last];
        this.items[last] = null;
        return result;
    }

    // return (but do not delete) a random item
    public Item sample() {
        if (this.isEmpty()) throw new NoSuchElementException();
        return this.items[N-1];
    }

    private class RandomizedQueueIterator implements Iterator<Item> {

        private RandomizedQueue<Item> copy;
        private int k;

        private RandomizedQueueIterator() {
            this.copy = new RandomizedQueue<Item>();
            for (int i = 0; i < RandomizedQueue.this.size(); i++) {
                this.copy.enqueue(RandomizedQueue.this.items[i]);
            }
        }

        @Override
        public boolean hasNext() {
            return k != this.copy.N;
        }

        @Override
        public Item next() {
            if (k == this.copy.N) {
                throw new NoSuchElementException();
            }
            return this.copy.items[k++];
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

    // return an independent iterator over items in random order
    @Override
    public Iterator<Item> iterator() {
        return new RandomizedQueueIterator();
    }

}
